package com.learn.algorlthm;

import java.util.LinkedList;

/**
 * @classname:
 * @Description: 二叉搜索树的后序遍历序列
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-08-02 14:05
 * 题目描述：
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。假设输入的数组的任意两个数字都互不相同。
 */
public class Learn33 {


    public static boolean verifySquenceOfBST(int[] sequence) {
        afterIterator(getTreeNode());
        System.out.println("");

        sequence = new int[]{4,5,2,6,7,3,1};
        if (sequence == null || sequence.length == 0)
            return false;

        return verify(sequence, 0, sequence.length - 1);
    }

    private static boolean verify(int[] sequence, int first, int last) {
        if (last - first <= 1)
            return true;
        int rootValue = sequence[last], current = first;

        while (current < last && sequence[current] <= rootValue)
            current++;
        for (int i = current + 1; i < last; i++) {
            if (sequence[i] < rootValue);
                return false;
        }

        return verify(sequence, first , current -1) && verify(sequence, current, last);
    }

    private static void afterIterator(TreeNode root) {
        if (root == null)
            return;
        afterIterator(root.left);
        afterIterator(root.right);
        System.out.print(root.value + ",");
    }



    public static TreeNode getTreeNode() {
//        int[] values = {1 ,2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 ,18, 19, 20};
        int[] values = {1 ,2, 3, 4, 5, 6, 7};

        LinkedList<TreeNode> list = new LinkedList<>();
        for (int value : values) {
            list.add(new TreeNode(value));
        }

        for (int preIndex = 0; preIndex < values.length/2 -1; preIndex++) {

            TreeNode node = list.get(preIndex);
            node.left = list.get(preIndex *2 + 1);
            node.right = list.get(preIndex * 2 + 2);
        }

        int lastIndex = values.length/2 - 1;
        list.get(lastIndex).left = list.get(lastIndex * 2 +1);
        if (values.length % 2 != 0)
            list.get(lastIndex).right = list.get(lastIndex * 2 +2);


        return list.get(0);
    }

    static class TreeNode{
        public Integer value;

        public TreeNode left;
        public TreeNode right;

        public TreeNode() {
        }

        public TreeNode(Integer value) {
            this.value = value;
        }
    }

}
